
<!DOCTYPE html>

<html>
  
<!-- Mirrored from docs.sympy.org/latest/modules/discrete.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:24:22 GMT -->
<!-- Added by HTTrack --><meta http-equiv="content-type" content="text/html;charset=utf-8" /><!-- /Added by HTTrack -->
<head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>Discrete &#8212; SymPy 1.9 documentation</title>
    <link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="../_static/default.css" />
    <link rel="stylesheet" type="text/css" href="../_static/graphviz.css" />
    <link rel="stylesheet" type="text/css" href="../_static/plot_directive.css" />
    <link rel="stylesheet" type="text/css" href="../../../live.sympy.org/static/live-core.css" />
    <link rel="stylesheet" type="text/css" href="../../../live.sympy.org/static/live-autocomplete.css" />
    <link rel="stylesheet" type="text/css" href="../../../live.sympy.org/static/live-sphinx.css" />
    
    <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
    <script src="../_static/jquery.js"></script>
    <script src="../_static/underscore.js"></script>
    <script src="../_static/doctools.js"></script>
    <script src="../../../live.sympy.org/static/utilities.js"></script>
    <script src="../../../live.sympy.org/static/external/classy.js"></script>
    <script src="../../../live.sympy.org/static/live-core.js"></script>
    <script src="../../../live.sympy.org/static/live-autocomplete.js"></script>
    <script src="../../../live.sympy.org/static/live-sphinx.js"></script>
    <script async="async" src="../../../cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest8331.js?config=TeX-AMS_HTML-full"></script>
    <script type="text/x-mathjax-config">MathJax.Hub.Config({"tex2jax": {"inlineMath": [["\\(", "\\)"]], "displayMath": [["\\[", "\\]"]]}})</script>
    
    <link rel="shortcut icon" href="../_static/sympy-notailtext-favicon.ico"/>
    <link href="discrete.html" rel="canonical" />
    
    <link rel="index" title="Index" href="../genindex.html" />
    <link rel="search" title="Search" href="../search.html" />
    <link rel="next" title="Numerical Evaluation" href="evalf.html" />
    <link rel="prev" title="Diophantine" href="solvers/diophantine.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="evalf.html" title="Numerical Evaluation"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="solvers/diophantine.html" title="Diophantine"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="index.html" accesskey="U">SymPy Modules Reference</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Discrete</a></li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="discrete">
<h1>Discrete<a class="headerlink" href="#discrete" title="Permalink to this headline">¶</a></h1>
<p>The <code class="docutils literal notranslate"><span class="pre">discrete</span></code> module in SymPy implements methods to compute discrete
transforms and convolutions of finite sequences.</p>
<span class="target" id="module-sympy.discrete"></span><p>This module contains functions which operate on discrete sequences.</p>
<dl class="simple">
<dt>Transforms - <code class="docutils literal notranslate"><span class="pre">fft</span></code>, <code class="docutils literal notranslate"><span class="pre">ifft</span></code>, <code class="docutils literal notranslate"><span class="pre">ntt</span></code>, <code class="docutils literal notranslate"><span class="pre">intt</span></code>, <code class="docutils literal notranslate"><span class="pre">fwht</span></code>, <code class="docutils literal notranslate"><span class="pre">ifwht</span></code>,</dt><dd><p><code class="docutils literal notranslate"><span class="pre">mobius_transform</span></code>, <code class="docutils literal notranslate"><span class="pre">inverse_mobius_transform</span></code></p>
</dd>
<dt>Convolutions - <code class="docutils literal notranslate"><span class="pre">convolution</span></code>, <code class="docutils literal notranslate"><span class="pre">convolution_fft</span></code>, <code class="docutils literal notranslate"><span class="pre">convolution_ntt</span></code>,</dt><dd><p><code class="docutils literal notranslate"><span class="pre">convolution_fwht</span></code>, <code class="docutils literal notranslate"><span class="pre">convolution_subset</span></code>,
<code class="docutils literal notranslate"><span class="pre">covering_product</span></code>, <code class="docutils literal notranslate"><span class="pre">intersecting_product</span></code></p>
</dd>
</dl>
<p>Since the discrete transforms can be used to reduce the computational complexity
of the discrete convolutions, the <code class="docutils literal notranslate"><span class="pre">convolutions</span></code> module makes use of the
<code class="docutils literal notranslate"><span class="pre">transforms</span></code> module for efficient computation (notable for long input sequences).</p>
<section id="module-sympy.discrete.transforms">
<span id="transforms"></span><h2>Transforms<a class="headerlink" href="#module-sympy.discrete.transforms" title="Permalink to this headline">¶</a></h2>
<p>This section lists the methods which implement the basic transforms
for discrete sequences.</p>
<section id="fast-fourier-transform">
<h3>Fast Fourier Transform<a class="headerlink" href="#fast-fourier-transform" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.fft">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">fft</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">dps</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L70-L116"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.fft" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Discrete Fourier Transform (<strong>DFT</strong>) in the complex domain.</p>
<p>The sequence is automatically padded to the right with zeros, as the
<em>radix-2 FFT</em> requires the number of sample points to be a power of 2.</p>
<p>This method should be used with default arguments only for short sequences
as the complexity of expressions increases with the size of the sequence.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which <strong>DFT</strong> is to be applied.</p>
</div></blockquote>
<p><strong>dps</strong> : Integer</p>
<blockquote>
<div><p>Specifies the number of decimal digits for precision.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">fft</span><span class="p">,</span> <span class="n">ifft</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">fft</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">])</span>
<span class="go">[10, -2 - 2*I, -2, -2 + 2*I]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ifft</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">ifft</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">])</span>
<span class="go">[5/2, -1/2 + I/2, -1/2, -1/2 - I/2]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fft</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">ifft</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">dps</span><span class="o">=</span><span class="mi">15</span><span class="p">)</span>
<span class="go">[3.75, -0.5 - 0.75*I, -1.75, -0.5 + 0.75*I]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fft</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1.0, 7.0, 3.0, 4.0]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r154"><span class="brackets"><a class="fn-backref" href="#id1">R154</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm">https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm</a></p>
</dd>
<dt class="label" id="r155"><span class="brackets"><a class="fn-backref" href="#id2">R155</a></span></dt>
<dd><p><a class="reference external" href="http://mathworld.wolfram.com/FastFourierTransform.html">http://mathworld.wolfram.com/FastFourierTransform.html</a></p>
</dd>
</dl>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.ifft">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">ifft</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">dps</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L119-L120"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.ifft" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Discrete Fourier Transform (<strong>DFT</strong>) in the complex domain.</p>
<p>The sequence is automatically padded to the right with zeros, as the
<em>radix-2 FFT</em> requires the number of sample points to be a power of 2.</p>
<p>This method should be used with default arguments only for short sequences
as the complexity of expressions increases with the size of the sequence.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which <strong>DFT</strong> is to be applied.</p>
</div></blockquote>
<p><strong>dps</strong> : Integer</p>
<blockquote>
<div><p>Specifies the number of decimal digits for precision.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">fft</span><span class="p">,</span> <span class="n">ifft</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">fft</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">])</span>
<span class="go">[10, -2 - 2*I, -2, -2 + 2*I]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ifft</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">ifft</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">])</span>
<span class="go">[5/2, -1/2 + I/2, -1/2, -1/2 - I/2]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fft</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">ifft</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">dps</span><span class="o">=</span><span class="mi">15</span><span class="p">)</span>
<span class="go">[3.75, -0.5 - 0.75*I, -1.75, -0.5 + 0.75*I]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fft</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1.0, 7.0, 3.0, 4.0]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r156"><span class="brackets"><a class="fn-backref" href="#id3">R156</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm">https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm</a></p>
</dd>
<dt class="label" id="r157"><span class="brackets"><a class="fn-backref" href="#id4">R157</a></span></dt>
<dd><p><a class="reference external" href="http://mathworld.wolfram.com/FastFourierTransform.html">http://mathworld.wolfram.com/FastFourierTransform.html</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="number-theoretic-transform">
<h3>Number Theoretic Transform<a class="headerlink" href="#number-theoretic-transform" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.ntt">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">ntt</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">prime</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L189-L229"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.ntt" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Number Theoretic Transform (<strong>NTT</strong>), which specializes the
Discrete Fourier Transform (<strong>DFT</strong>) over quotient ring <span class="math notranslate nohighlight">\(Z/pZ\)</span> for prime
<span class="math notranslate nohighlight">\(p\)</span> instead of complex numbers <span class="math notranslate nohighlight">\(C\)</span>.</p>
<p>The sequence is automatically padded to the right with zeros, as the
<em>radix-2 NTT</em> requires the number of sample points to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which <strong>DFT</strong> is to be applied.</p>
</div></blockquote>
<p><strong>prime</strong> : Integer</p>
<blockquote>
<div><p>Prime modulus of the form <span class="math notranslate nohighlight">\((m 2^k + 1)\)</span> to be used for performing
<strong>NTT</strong> on the sequence.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">ntt</span><span class="p">,</span> <span class="n">intt</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ntt</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[10, 643, 767, 122]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">intt</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">intt</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[387, 415, 384, 353]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ntt</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="n">prime</span><span class="o">=</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r158"><span class="brackets"><a class="fn-backref" href="#id5">R158</a></span></dt>
<dd><p><a class="reference external" href="http://www.apfloat.org/ntt.html">http://www.apfloat.org/ntt.html</a></p>
</dd>
<dt class="label" id="r159"><span class="brackets"><a class="fn-backref" href="#id6">R159</a></span></dt>
<dd><p><a class="reference external" href="http://mathworld.wolfram.com/NumberTheoreticTransform.html">http://mathworld.wolfram.com/NumberTheoreticTransform.html</a></p>
</dd>
<dt class="label" id="r160"><span class="brackets"><a class="fn-backref" href="#id7">R160</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)">https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29</a></p>
</dd>
</dl>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.intt">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">intt</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">prime</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L232-L233"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.intt" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Number Theoretic Transform (<strong>NTT</strong>), which specializes the
Discrete Fourier Transform (<strong>DFT</strong>) over quotient ring <span class="math notranslate nohighlight">\(Z/pZ\)</span> for prime
<span class="math notranslate nohighlight">\(p\)</span> instead of complex numbers <span class="math notranslate nohighlight">\(C\)</span>.</p>
<p>The sequence is automatically padded to the right with zeros, as the
<em>radix-2 NTT</em> requires the number of sample points to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which <strong>DFT</strong> is to be applied.</p>
</div></blockquote>
<p><strong>prime</strong> : Integer</p>
<blockquote>
<div><p>Prime modulus of the form <span class="math notranslate nohighlight">\((m 2^k + 1)\)</span> to be used for performing
<strong>NTT</strong> on the sequence.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">ntt</span><span class="p">,</span> <span class="n">intt</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ntt</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[10, 643, 767, 122]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">intt</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">intt</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[387, 415, 384, 353]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ntt</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="n">prime</span><span class="o">=</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">8</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r161"><span class="brackets"><a class="fn-backref" href="#id8">R161</a></span></dt>
<dd><p><a class="reference external" href="http://www.apfloat.org/ntt.html">http://www.apfloat.org/ntt.html</a></p>
</dd>
<dt class="label" id="r162"><span class="brackets"><a class="fn-backref" href="#id9">R162</a></span></dt>
<dd><p><a class="reference external" href="http://mathworld.wolfram.com/NumberTheoreticTransform.html">http://mathworld.wolfram.com/NumberTheoreticTransform.html</a></p>
</dd>
<dt class="label" id="r163"><span class="brackets"><a class="fn-backref" href="#id10">R163</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)">https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="fast-walsh-hadamard-transform">
<h3>Fast Walsh Hadamard Transform<a class="headerlink" href="#fast-walsh-hadamard-transform" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.fwht">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">fwht</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L275-L311"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.fwht" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Walsh Hadamard Transform (<strong>WHT</strong>), and uses Hadamard
ordering for the sequence.</p>
<p>The sequence is automatically padded to the right with zeros, as the
<em>radix-2 FWHT</em> requires the number of sample points to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which WHT is to be applied.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">fwht</span><span class="p">,</span> <span class="n">ifwht</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fwht</span><span class="p">([</span><span class="mi">4</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="o">-</span><span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">])</span>
<span class="go">[8, 0, 8, 0, 8, 8, 0, 0]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ifwht</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[4, 2, 2, 0, 0, 2, -2, 0]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">ifwht</span><span class="p">([</span><span class="mi">19</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">11</span><span class="p">,</span> <span class="o">-</span><span class="mi">9</span><span class="p">,</span> <span class="o">-</span><span class="mi">7</span><span class="p">,</span> <span class="mi">13</span><span class="p">,</span> <span class="o">-</span><span class="mi">15</span><span class="p">,</span> <span class="mi">5</span><span class="p">])</span>
<span class="go">[2, 0, 4, 0, 3, 10, 0, 0]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fwht</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[19, -1, 11, -9, -7, 13, -15, 5]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r164"><span class="brackets"><a class="fn-backref" href="#id11">R164</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Hadamard_transform">https://en.wikipedia.org/wiki/Hadamard_transform</a></p>
</dd>
<dt class="label" id="r165"><span class="brackets"><a class="fn-backref" href="#id12">R165</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Fast_Walsh–Hadamard_transform">https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform</a></p>
</dd>
</dl>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.ifwht">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">ifwht</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L314-L315"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.ifwht" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Walsh Hadamard Transform (<strong>WHT</strong>), and uses Hadamard
ordering for the sequence.</p>
<p>The sequence is automatically padded to the right with zeros, as the
<em>radix-2 FWHT</em> requires the number of sample points to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which WHT is to be applied.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">fwht</span><span class="p">,</span> <span class="n">ifwht</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fwht</span><span class="p">([</span><span class="mi">4</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="o">-</span><span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">])</span>
<span class="go">[8, 0, 8, 0, 8, 8, 0, 0]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">ifwht</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[4, 2, 2, 0, 0, 2, -2, 0]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">ifwht</span><span class="p">([</span><span class="mi">19</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">11</span><span class="p">,</span> <span class="o">-</span><span class="mi">9</span><span class="p">,</span> <span class="o">-</span><span class="mi">7</span><span class="p">,</span> <span class="mi">13</span><span class="p">,</span> <span class="o">-</span><span class="mi">15</span><span class="p">,</span> <span class="mi">5</span><span class="p">])</span>
<span class="go">[2, 0, 4, 0, 3, 10, 0, 0]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">fwht</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[19, -1, 11, -9, -7, 13, -15, 5]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r166"><span class="brackets"><a class="fn-backref" href="#id13">R166</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Hadamard_transform">https://en.wikipedia.org/wiki/Hadamard_transform</a></p>
</dd>
<dt class="label" id="r167"><span class="brackets"><a class="fn-backref" href="#id14">R167</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Fast_Walsh–Hadamard_transform">https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="mobius-transform">
<h3>Möbius Transform<a class="headerlink" href="#mobius-transform" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.mobius_transform">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">mobius_transform</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">subset</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">True</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L364-L420"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.mobius_transform" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Mobius Transform for subset lattice with indices of
sequence as bitmasks.</p>
<p>The indices of each argument, considered as bit strings, correspond
to subsets of a finite set.</p>
<p>The sequence is automatically padded to the right with zeros, as the
definition of subset/superset based on bitmasks (indices) requires
the size of sequence to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which Mobius Transform is to be applied.</p>
</div></blockquote>
<p><strong>subset</strong> : bool</p>
<blockquote>
<div><p>Specifies if Mobius Transform is applied by enumerating subsets
or supersets of the given set.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">symbols</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">mobius_transform</span><span class="p">,</span> <span class="n">inverse_mobius_transform</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">symbols</span><span class="p">(</span><span class="s1">&#39;x y z&#39;</span><span class="p">)</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">])</span>
<span class="go">[x, x + y, x + z, x + y + z]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[x, y, z, 0]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[x + y + z, y, z, 0]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[x, y, z, 0]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">])</span>
<span class="go">[1, 3, 4, 10]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[10, 6, 7, 4]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r168"><span class="brackets"><a class="fn-backref" href="#id15">R168</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Möbius_inversion_formula">https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula</a></p>
</dd>
<dt class="label" id="r169"><span class="brackets"><a class="fn-backref" href="#id16">R169</a></span></dt>
<dd><p><a class="reference external" href="https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf">https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf</a></p>
</dd>
<dt class="label" id="r170"><span class="brackets"><a class="fn-backref" href="#id17">R170</a></span></dt>
<dd><p><a class="reference external" href="https://arxiv.org/pdf/1211.0189.pdf">https://arxiv.org/pdf/1211.0189.pdf</a></p>
</dd>
</dl>
</dd></dl>

<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.transforms.inverse_mobius_transform">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.transforms.</span></span><span class="sig-name descname"><span class="pre">inverse_mobius_transform</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">seq</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">subset</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">True</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/transforms.py#L422-L423"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.transforms.inverse_mobius_transform" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs the Mobius Transform for subset lattice with indices of
sequence as bitmasks.</p>
<p>The indices of each argument, considered as bit strings, correspond
to subsets of a finite set.</p>
<p>The sequence is automatically padded to the right with zeros, as the
definition of subset/superset based on bitmasks (indices) requires
the size of sequence to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>seq</strong> : iterable</p>
<blockquote>
<div><p>The sequence on which Mobius Transform is to be applied.</p>
</div></blockquote>
<p><strong>subset</strong> : bool</p>
<blockquote>
<div><p>Specifies if Mobius Transform is applied by enumerating subsets
or supersets of the given set.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">symbols</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">mobius_transform</span><span class="p">,</span> <span class="n">inverse_mobius_transform</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">symbols</span><span class="p">(</span><span class="s1">&#39;x y z&#39;</span><span class="p">)</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">])</span>
<span class="go">[x, x + y, x + z, x + y + z]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[x, y, z, 0]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[x + y + z, y, z, 0]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[x, y, z, 0]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">])</span>
<span class="go">[1, 3, 4, 10]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">mobius_transform</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[10, 6, 7, 4]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">inverse_mobius_transform</span><span class="p">(</span><span class="n">_</span><span class="p">,</span> <span class="n">subset</span><span class="o">=</span><span class="kc">False</span><span class="p">)</span>
<span class="go">[1, 2, 3, 4]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r171"><span class="brackets"><a class="fn-backref" href="#id18">R171</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Möbius_inversion_formula">https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula</a></p>
</dd>
<dt class="label" id="r172"><span class="brackets"><a class="fn-backref" href="#id19">R172</a></span></dt>
<dd><p><a class="reference external" href="https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf">https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf</a></p>
</dd>
<dt class="label" id="r173"><span class="brackets"><a class="fn-backref" href="#id20">R173</a></span></dt>
<dd><p><a class="reference external" href="https://arxiv.org/pdf/1211.0189.pdf">https://arxiv.org/pdf/1211.0189.pdf</a></p>
</dd>
</dl>
</dd></dl>

</section>
</section>
<section id="module-sympy.discrete.convolutions">
<span id="convolutions"></span><h2>Convolutions<a class="headerlink" href="#module-sympy.discrete.convolutions" title="Permalink to this headline">¶</a></h2>
<p>This section lists the methods which implement the basic convolutions
for discrete sequences.</p>
<section id="convolution">
<h3>Convolution<a class="headerlink" href="#convolution" title="Permalink to this headline">¶</a></h3>
<p>This is a general method for calculating the convolution of discrete
sequences, which internally calls one of the methods <code class="docutils literal notranslate"><span class="pre">convolution_fft</span></code>,
<code class="docutils literal notranslate"><span class="pre">convolution_ntt</span></code>, <code class="docutils literal notranslate"><span class="pre">convolution_fwht</span></code>, or <code class="docutils literal notranslate"><span class="pre">convolution_subset</span></code>.</p>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.convolutions.convolution">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.convolutions.</span></span><span class="sig-name descname"><span class="pre">convolution</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">b</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">cycle</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">0</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">dps</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">prime</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">dyadic</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">subset</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/convolutions.py#L14-L93"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.convolutions.convolution" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs convolution by determining the type of desired
convolution using hints.</p>
<p>Exactly one of <code class="docutils literal notranslate"><span class="pre">dps</span></code>, <code class="docutils literal notranslate"><span class="pre">prime</span></code>, <code class="docutils literal notranslate"><span class="pre">dyadic</span></code>, <code class="docutils literal notranslate"><span class="pre">subset</span></code> arguments
should be specified explicitly for identifying the type of convolution,
and the argument <code class="docutils literal notranslate"><span class="pre">cycle</span></code> can be specified optionally.</p>
<p>For the default arguments, linear convolution is performed using <strong>FFT</strong>.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>a, b</strong> : iterables</p>
<blockquote>
<div><p>The sequences for which convolution is performed.</p>
</div></blockquote>
<p><strong>cycle</strong> : Integer</p>
<blockquote>
<div><p>Specifies the length for doing cyclic convolution.</p>
</div></blockquote>
<p><strong>dps</strong> : Integer</p>
<blockquote>
<div><p>Specifies the number of decimal digits for precision for
performing <strong>FFT</strong> on the sequence.</p>
</div></blockquote>
<p><strong>prime</strong> : Integer</p>
<blockquote>
<div><p>Prime modulus of the form <span class="math notranslate nohighlight">\((m 2^k + 1)\)</span> to be used for
performing <strong>NTT</strong> on the sequence.</p>
</div></blockquote>
<p><strong>dyadic</strong> : bool</p>
<blockquote>
<div><p>Identifies the convolution type as dyadic (<em>bitwise-XOR</em>)
convolution, which is performed using <strong>FWHT</strong>.</p>
</div></blockquote>
<p><strong>subset</strong> : bool</p>
<blockquote>
<div><p>Identifies the convolution type as subset convolution.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">convolution</span><span class="p">,</span> <span class="n">symbols</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">I</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">symbols</span><span class="p">(</span><span class="s1">&#39;u v w x y z&#39;</span><span class="p">)</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="mi">1</span> <span class="o">+</span> <span class="mi">2</span><span class="o">*</span><span class="n">I</span><span class="p">,</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">3</span><span class="o">*</span><span class="n">I</span><span class="p">],</span> <span class="p">[</span><span class="n">S</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span><span class="o">/</span><span class="mi">4</span><span class="p">,</span> <span class="mi">6</span><span class="p">],</span> <span class="n">dps</span><span class="o">=</span><span class="mi">3</span><span class="p">)</span>
<span class="go">[1.25 + 2.5*I, 11.0 + 15.8*I, 24.0 + 18.0*I]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">],</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">6</span><span class="p">],</span> <span class="n">cycle</span><span class="o">=</span><span class="mi">3</span><span class="p">)</span>
<span class="go">[31, 31, 28]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="mi">111</span><span class="p">,</span> <span class="mi">777</span><span class="p">],</span> <span class="p">[</span><span class="mi">888</span><span class="p">,</span> <span class="mi">444</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">19</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">10</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[1283, 19351, 14219]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="mi">111</span><span class="p">,</span> <span class="mi">777</span><span class="p">],</span> <span class="p">[</span><span class="mi">888</span><span class="p">,</span> <span class="mi">444</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">19</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">10</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">cycle</span><span class="o">=</span><span class="mi">2</span><span class="p">)</span>
<span class="go">[15502, 19351]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">dyadic</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
<span class="go">[u*x + v*y, u*y + v*x, u*z, v*z]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">dyadic</span><span class="o">=</span><span class="kc">True</span><span class="p">,</span> <span class="n">cycle</span><span class="o">=</span><span class="mi">2</span><span class="p">)</span>
<span class="go">[u*x + u*z + v*y, u*y + v*x + v*z]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">subset</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
<span class="go">[u*x, u*y + v*x, u*z + w*x, v*z + w*y]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">subset</span><span class="o">=</span><span class="kc">True</span><span class="p">,</span> <span class="n">cycle</span><span class="o">=</span><span class="mi">3</span><span class="p">)</span>
<span class="go">[u*x + v*z + w*y, u*y + v*x, u*z + w*x]</span>
</pre></div>
</div>
</dd></dl>

</section>
<section id="convolution-using-fast-fourier-transform">
<h3>Convolution using Fast Fourier Transform<a class="headerlink" href="#convolution-using-fast-fourier-transform" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.convolutions.convolution_fft">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.convolutions.</span></span><span class="sig-name descname"><span class="pre">convolution_fft</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">b</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">dps</span></span><span class="o"><span class="pre">=</span></span><span class="default_value"><span class="pre">None</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/convolutions.py#L102-L149"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.convolutions.convolution_fft" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs linear convolution using Fast Fourier Transform.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>a, b</strong> : iterables</p>
<blockquote>
<div><p>The sequences for which convolution is performed.</p>
</div></blockquote>
<p><strong>dps</strong> : Integer</p>
<blockquote>
<div><p>Specifies the number of decimal digits for precision.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">S</span><span class="p">,</span> <span class="n">I</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.discrete.convolutions</span> <span class="kn">import</span> <span class="n">convolution_fft</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_fft</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">],</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">])</span>
<span class="go">[8, 22, 15]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_fft</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">5</span><span class="p">],</span> <span class="p">[</span><span class="mi">6</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">3</span><span class="p">])</span>
<span class="go">[12, 44, 41, 15]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_fft</span><span class="p">([</span><span class="mi">1</span> <span class="o">+</span> <span class="mi">2</span><span class="o">*</span><span class="n">I</span><span class="p">,</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">3</span><span class="o">*</span><span class="n">I</span><span class="p">],</span> <span class="p">[</span><span class="n">S</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span><span class="o">/</span><span class="mi">4</span><span class="p">,</span> <span class="mi">6</span><span class="p">])</span>
<span class="go">[5/4 + 5*I/2, 11 + 63*I/4, 24 + 18*I]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r174"><span class="brackets"><a class="fn-backref" href="#id21">R174</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Convolution_theorem">https://en.wikipedia.org/wiki/Convolution_theorem</a></p>
</dd>
<dt class="label" id="r175"><span class="brackets"><a class="fn-backref" href="#id22">R175</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)">https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="convolution-using-number-theoretic-transform">
<h3>Convolution using Number Theoretic Transform<a class="headerlink" href="#convolution-using-number-theoretic-transform" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.convolutions.convolution_ntt">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.convolutions.</span></span><span class="sig-name descname"><span class="pre">convolution_ntt</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">b</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">prime</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/convolutions.py#L158-L204"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.convolutions.convolution_ntt" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs linear convolution using Number Theoretic Transform.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>a, b</strong> : iterables</p>
<blockquote>
<div><p>The sequences for which convolution is performed.</p>
</div></blockquote>
<p><strong>prime</strong> : Integer</p>
<blockquote>
<div><p>Prime modulus of the form <span class="math notranslate nohighlight">\((m 2^k + 1)\)</span> to be used for performing
<strong>NTT</strong> on the sequence.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.discrete.convolutions</span> <span class="kn">import</span> <span class="n">convolution_ntt</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_ntt</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">],</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">19</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">10</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[8, 22, 15]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_ntt</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">5</span><span class="p">],</span> <span class="p">[</span><span class="mi">6</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">3</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">19</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">10</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[12, 44, 41, 15]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_ntt</span><span class="p">([</span><span class="mi">333</span><span class="p">,</span> <span class="mi">555</span><span class="p">],</span> <span class="p">[</span><span class="mi">222</span><span class="p">,</span> <span class="mi">666</span><span class="p">],</span> <span class="n">prime</span><span class="o">=</span><span class="mi">19</span><span class="o">*</span><span class="mi">2</span><span class="o">**</span><span class="mi">10</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<span class="go">[15555, 14219, 19404]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r176"><span class="brackets"><a class="fn-backref" href="#id23">R176</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Convolution_theorem">https://en.wikipedia.org/wiki/Convolution_theorem</a></p>
</dd>
<dt class="label" id="r177"><span class="brackets"><a class="fn-backref" href="#id24">R177</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)">https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general%29</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="convolution-using-fast-walsh-hadamard-transform">
<h3>Convolution using Fast Walsh Hadamard Transform<a class="headerlink" href="#convolution-using-fast-walsh-hadamard-transform" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.convolutions.convolution_fwht">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.convolutions.</span></span><span class="sig-name descname"><span class="pre">convolution_fwht</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">b</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/convolutions.py#L213-L270"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.convolutions.convolution_fwht" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs dyadic (<em>bitwise-XOR</em>) convolution using Fast Walsh Hadamard
Transform.</p>
<p>The convolution is automatically padded to the right with zeros, as the
<em>radix-2 FWHT</em> requires the number of sample points to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>a, b</strong> : iterables</p>
<blockquote>
<div><p>The sequences for which convolution is performed.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">symbols</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">I</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.discrete.convolutions</span> <span class="kn">import</span> <span class="n">convolution_fwht</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">symbols</span><span class="p">(</span><span class="s1">&#39;u v x y&#39;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_fwht</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">])</span>
<span class="go">[u*x + v*y, u*y + v*x]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_fwht</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">],</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">])</span>
<span class="go">[23, 22]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_fwht</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">5</span> <span class="o">+</span> <span class="mi">4</span><span class="o">*</span><span class="n">I</span><span class="p">,</span> <span class="mi">7</span><span class="p">],</span> <span class="p">[</span><span class="mi">6</span><span class="o">*</span><span class="n">I</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">3</span> <span class="o">+</span> <span class="mi">4</span><span class="o">*</span><span class="n">I</span><span class="p">])</span>
<span class="go">[56 + 68*I, -10 + 30*I, 6 + 50*I, 48 + 32*I]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_fwht</span><span class="p">([</span><span class="n">S</span><span class="p">(</span><span class="mi">33</span><span class="p">)</span><span class="o">/</span><span class="mi">7</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">55</span><span class="p">)</span><span class="o">/</span><span class="mi">6</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">7</span><span class="p">)</span><span class="o">/</span><span class="mi">4</span><span class="p">],</span> <span class="p">[</span><span class="n">S</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span><span class="o">/</span><span class="mi">3</span><span class="p">,</span> <span class="mi">5</span><span class="p">])</span>
<span class="go">[2057/42, 1870/63, 7/6, 35/4]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r178"><span class="brackets"><a class="fn-backref" href="#id25">R178</a></span></dt>
<dd><p><a class="reference external" href="https://www.radioeng.cz/fulltexts/2002/02_03_40_42.pdf">https://www.radioeng.cz/fulltexts/2002/02_03_40_42.pdf</a></p>
</dd>
<dt class="label" id="r179"><span class="brackets"><a class="fn-backref" href="#id26">R179</a></span></dt>
<dd><p><a class="reference external" href="https://en.wikipedia.org/wiki/Hadamard_transform">https://en.wikipedia.org/wiki/Hadamard_transform</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="subset-convolution">
<h3>Subset Convolution<a class="headerlink" href="#subset-convolution" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.convolutions.convolution_subset">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.convolutions.</span></span><span class="sig-name descname"><span class="pre">convolution_subset</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">b</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/convolutions.py#L279-L347"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.convolutions.convolution_subset" title="Permalink to this definition">¶</a></dt>
<dd><p>Performs Subset Convolution of given sequences.</p>
<p>The indices of each argument, considered as bit strings, correspond to
subsets of a finite set.</p>
<p>The sequence is automatically padded to the right with zeros, as the
definition of subset based on bitmasks (indices) requires the size of
sequence to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>a, b</strong> : iterables</p>
<blockquote>
<div><p>The sequences for which convolution is performed.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">symbols</span><span class="p">,</span> <span class="n">S</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.discrete.convolutions</span> <span class="kn">import</span> <span class="n">convolution_subset</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">symbols</span><span class="p">(</span><span class="s1">&#39;u v x y z&#39;</span><span class="p">)</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_subset</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">])</span>
<span class="go">[u*x, u*y + v*x]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_subset</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">],</span> <span class="p">[</span><span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">])</span>
<span class="go">[u*y, u*z + v*y, x*y, x*z]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_subset</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span><span class="o">/</span><span class="mi">3</span><span class="p">],</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">])</span>
<span class="go">[3, 6]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">convolution_subset</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span><span class="o">/</span><span class="mi">7</span><span class="p">],</span> <span class="p">[</span><span class="mi">7</span><span class="p">])</span>
<span class="go">[7, 21, 5, 0]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r180"><span class="brackets"><a class="fn-backref" href="#id27">R180</a></span></dt>
<dd><p><a class="reference external" href="https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf">https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="covering-product">
<h3>Covering Product<a class="headerlink" href="#covering-product" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.convolutions.covering_product">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.convolutions.</span></span><span class="sig-name descname"><span class="pre">covering_product</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">b</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/convolutions.py#L356-L417"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.convolutions.covering_product" title="Permalink to this definition">¶</a></dt>
<dd><p>Returns the covering product of given sequences.</p>
<p>The indices of each argument, considered as bit strings, correspond to
subsets of a finite set.</p>
<p>The covering product of given sequences is a sequence which contains
the sum of products of the elements of the given sequences grouped by
the <em>bitwise-OR</em> of the corresponding indices.</p>
<p>The sequence is automatically padded to the right with zeros, as the
definition of subset based on bitmasks (indices) requires the size of
sequence to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>a, b</strong> : iterables</p>
<blockquote>
<div><p>The sequences for which covering product is to be obtained.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">symbols</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="n">covering_product</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">symbols</span><span class="p">(</span><span class="s1">&#39;u v x y z&#39;</span><span class="p">)</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">covering_product</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">])</span>
<span class="go">[u*x, u*y + v*x + v*y]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">covering_product</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">],</span> <span class="p">[</span><span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">])</span>
<span class="go">[u*y, u*z + v*y + v*z, x*y, x*z]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">covering_product</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span><span class="o">/</span><span class="mi">3</span><span class="p">],</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">5</span><span class="o">*</span><span class="n">I</span><span class="p">])</span>
<span class="go">[3, 26/3 + 25*I/3]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">covering_product</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span><span class="o">/</span><span class="mi">7</span><span class="p">],</span> <span class="p">[</span><span class="mi">7</span><span class="p">,</span> <span class="mi">8</span><span class="p">])</span>
<span class="go">[7, 53, 5, 40/7]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r181"><span class="brackets"><a class="fn-backref" href="#id28">R181</a></span></dt>
<dd><p><a class="reference external" href="https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf">https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf</a></p>
</dd>
</dl>
</dd></dl>

</section>
<section id="intersecting-product">
<h3>Intersecting Product<a class="headerlink" href="#intersecting-product" title="Permalink to this headline">¶</a></h3>
<dl class="py function">
<dt class="sig sig-object py" id="sympy.discrete.convolutions.intersecting_product">
<span class="sig-prename descclassname"><span class="pre">sympy.discrete.convolutions.</span></span><span class="sig-name descname"><span class="pre">intersecting_product</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">a</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">b</span></span></em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/sympy/sympy/blob/00d6469eafdd4aac346a0b598184c15f2560dbe5/sympy/discrete/convolutions.py#L426-L487"><span class="viewcode-link"><span class="pre">[source]</span></span></a><a class="headerlink" href="#sympy.discrete.convolutions.intersecting_product" title="Permalink to this definition">¶</a></dt>
<dd><p>Returns the intersecting product of given sequences.</p>
<p>The indices of each argument, considered as bit strings, correspond to
subsets of a finite set.</p>
<p>The intersecting product of given sequences is the sequence which
contains the sum of products of the elements of the given sequences
grouped by the <em>bitwise-AND</em> of the corresponding indices.</p>
<p>The sequence is automatically padded to the right with zeros, as the
definition of subset based on bitmasks (indices) requires the size of
sequence to be a power of 2.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><p><strong>a, b</strong> : iterables</p>
<blockquote>
<div><p>The sequences for which intersecting product is to be obtained.</p>
</div></blockquote>
</dd>
</dl>
<p class="rubric">Examples</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy</span> <span class="kn">import</span> <span class="n">symbols</span><span class="p">,</span> <span class="n">S</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="n">intersecting_product</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">symbols</span><span class="p">(</span><span class="s1">&#39;u v x y z&#39;</span><span class="p">)</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">intersecting_product</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">],</span> <span class="p">[</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">])</span>
<span class="go">[u*x + u*y + v*x, v*y]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">intersecting_product</span><span class="p">([</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">],</span> <span class="p">[</span><span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">])</span>
<span class="go">[u*y + u*z + v*y + x*y + x*z, v*z, 0, 0]</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">intersecting_product</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span><span class="o">/</span><span class="mi">3</span><span class="p">],</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">4</span> <span class="o">+</span> <span class="mi">5</span><span class="o">*</span><span class="n">I</span><span class="p">])</span>
<span class="go">[9 + 5*I, 8/3 + 10*I/3]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">intersecting_product</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="n">S</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span><span class="o">/</span><span class="mi">7</span><span class="p">],</span> <span class="p">[</span><span class="mi">7</span><span class="p">,</span> <span class="mi">8</span><span class="p">])</span>
<span class="go">[327/7, 24, 0, 0]</span>
</pre></div>
</div>
<p class="rubric">References</p>
<dl class="citation">
<dt class="label" id="r182"><span class="brackets"><a class="fn-backref" href="#id29">R182</a></span></dt>
<dd><p><a class="reference external" href="https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf">https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf</a></p>
</dd>
</dl>
</dd></dl>

</section>
</section>
</section>


            <div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="../index.html">
              <img class="logo" src="../_static/sympylogo.png" alt="Logo"/>
            </a></p>
  <h3><a href="../index.html">Table of Contents</a></h3>
  <ul>
<li><a class="reference internal" href="#">Discrete</a><ul>
<li><a class="reference internal" href="#module-sympy.discrete.transforms">Transforms</a><ul>
<li><a class="reference internal" href="#fast-fourier-transform">Fast Fourier Transform</a></li>
<li><a class="reference internal" href="#number-theoretic-transform">Number Theoretic Transform</a></li>
<li><a class="reference internal" href="#fast-walsh-hadamard-transform">Fast Walsh Hadamard Transform</a></li>
<li><a class="reference internal" href="#mobius-transform">Möbius Transform</a></li>
</ul>
</li>
<li><a class="reference internal" href="#module-sympy.discrete.convolutions">Convolutions</a><ul>
<li><a class="reference internal" href="#convolution">Convolution</a></li>
<li><a class="reference internal" href="#convolution-using-fast-fourier-transform">Convolution using Fast Fourier Transform</a></li>
<li><a class="reference internal" href="#convolution-using-number-theoretic-transform">Convolution using Number Theoretic Transform</a></li>
<li><a class="reference internal" href="#convolution-using-fast-walsh-hadamard-transform">Convolution using Fast Walsh Hadamard Transform</a></li>
<li><a class="reference internal" href="#subset-convolution">Subset Convolution</a></li>
<li><a class="reference internal" href="#covering-product">Covering Product</a></li>
<li><a class="reference internal" href="#intersecting-product">Intersecting Product</a></li>
</ul>
</li>
</ul>
</li>
</ul>

  <h4>Previous topic</h4>
  <p class="topless"><a href="solvers/diophantine.html"
                        title="previous chapter">Diophantine</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="evalf.html"
                        title="next chapter">Numerical Evaluation</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../_sources/modules/discrete.rst.txt"
            rel="nofollow">Show Source</a></li>
    </ul>
   </div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="https://docs.sympy.org/latest/search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="evalf.html" title="Numerical Evaluation"
             >next</a> |</li>
        <li class="right" >
          <a href="solvers/diophantine.html" title="Diophantine"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="index.html" >SymPy Modules Reference</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Discrete</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2021 SymPy Development Team.
      Last updated on Sep 30, 2021.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.1.2.
    </div>
  </body>

<!-- Mirrored from docs.sympy.org/latest/modules/discrete.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:24:22 GMT -->
</html>